package interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import data_structure.BTNode;

public class Interview_day2 {
	
	private static int[][] rectangle = null;
	/**
	 * Given an integer array, output all pairs that sum up to a specific value k
	 */
	public static List<int[]> arrayPairSum(int[] a, int target){
		Arrays.sort(a);
		int low = 0, high = a.length - 1;
		List<int[]> res = new ArrayList<int[]>();
		
		while(low < high){
			int sum = a[low] + a[high];
			if(sum == target){
				int[] r = new int[2];
				r[0] = a[low];
				r[1] = a[high];
				res.add(r);
			}else if(sum > target) high--;
			else low++;
		}
		
		return res;
	}
	
	/**
	 * Given a matrix of integers and coordinates of a rectangular region within the matrix, 
	 * find the sum of numbers falling inside the rectangle. 
	 * * *Our program will be called multiple times 
	 * with different rectangular regions from the same matrix.
	 * 
	 * Analysis:
	 * At first glance, the solution would be writing a double nested for loop and sum up
	 * and this has O(mn) complexity. However, we should focus on the description:  
	 * "be called multiple times from the same matrix".
	 * This indicates we should precompute and cache some data in order to reduce the 
	 * complexity.
	 * Precomputing and caching the sums of all rectangles results in O(1), but it uses a lot of space.
	 * And the space would be like: O(m^2n^2)
	 * 
	 * however, give (x1,y1), (x2,y2)
	 * we can: Area{(x1,y1), (x2,y2)} = 
	 *              Area{(0,0), (x2,y2)} + Area{(0,0), (x1,y1)}
	 *              - Area{(0,0), (x1,y2)} - Area{(0,0), (x2,y1)}
	 * We just need to store the area of every rectangle with left upper point be (0,0)
	 * 
	 * @param matrix
	 * @param leftup
	 * @param rightdown
	 * @return
	 */
	public static int matrixRegioinSum(int[][] matrix, int[] leftup, int[] rightdown){
		loadMatrix(matrix);
		return rectangle[leftup[0]][leftup[1]] + rectangle[rightdown[0]][rightdown[1]]
				- rectangle[leftup[0]][rightdown[1]] - rectangle[rightdown[0]][leftup[1]];
	}
	
	private static void loadMatrix(int[][] matrix){
		if(rectangle != null) return;
		rectangle = new int[matrix.length][matrix[0].length];
		for(int i = 0 ; i < matrix.length ; i++)
			for(int j = 0 ; j < matrix[0].length ; j++)
				rectangle[i][j] = (i+1) * (j+1);
	}
	
	/**
	 * Given an array of integers (positive and negative) find the largest continuous sum.
	 * It's also recognized as maximum sub-array problem to find the continuous subarray
	 * within a one-dimensional array of numbers.
	 * Ex: for[-2,1,-3,4,-1,2,1,-5,4]
	 *   the answer is: [4,-1,2,1]
	 *   
	 *   Note that we don’t reset the current sum to 0 
	 *   because the array can contain all negative integers. 
	 *   Then the result would be the largest negative number.
	 *   
	 *   current sum means the current maximum sum ended at i
	 *   max sum ended at i = max(max sum ended at i-1 + a[i], a[i]);
	 *   max sum = max(max sum ended from 0 to i)
	 * @param a
	 * @return
	 */
	public static int largestContinuousSum(int[] a){
		int maxSum = a[0], currentSum = a[0];
		//int begin = 0 , tempBegin = 0, end = 0 ;
		for(int i = 1 ; i < a.length ; i++){
			currentSum = Math.max(currentSum+a[i], a[i]);
			//if(currentSum + a[i] < a[i]) tempBegin = i;
			maxSum = Math.max(currentSum, maxSum);
			//if(currentSum > maxSum){
			//begin = tempBegin;
			//end = i;}
		}
		return maxSum;
	}

	
	/**
	 * There is an array of non-negative integers. 
	 * A second array is formed by shuffling the elements of the first array and deleting a random element. 
	 * Given these two arrays, find which element is missing in the second array.
	 * 
	 * Analysis:
	 * Method 1:
	 * Sort a
	 * Do a binary search in a
	 * But when there exists duplicate elements, thing can be complicated
	 * 
	 * Method 2:
	 * Sort a and b and iterate both O(nlgn)
	 * 
	 * Method 3:
	 * Use a hashtable<Integer, Integer> to store value of a and number of occurrence
	 * and iterate b and reduce the number to see what is left O(n) and O(n) space
	 * 
	 * Method 4:
	 * Summing up a and b and subtract them
	 * But not suitable for huge arrays in which the sum would overflow
	 * 
	 * Method 5: (Best, see below)
	 * XOR:
	 * m XOR m = 0
	 * m XOR 0 = m
	 * @param a
	 * @param b
	 * @return
	 */
	public static int findMissingElement(int[] a, int[] b){
		int result = 0;
		for(int i = 0 ; i < a.length ; i++)
			result ^= a[i];
		for(int i = 0 ; i < b.length ; i++)
			result ^= b[i];
		return result;
	}
	
	/**
	 * Given a linkedlist of integers and an integer value, 
	 * delete every node of the linkedlist containing that value.
	 * 
	 * Analysis:
	 * the corner case occurs when we need to delete head of the list
	 * and then we need to return a new head.
	 * @param head
	 * @param tar
	 */
	public static void linkedListRemoveNodes(ListNode head, int tar){
		ListNode fa = new ListNode(null);
		fa.next = head;
		ListNode ind = head;
		ListNode pre = fa;
		while(ind != null){
			if((int)ind.val ==  tar)
				pre.next = ind.next; 
			else pre = ind;
			ind = ind.next;
		}
		
		ListNode newhead = fa.next;
		ind = newhead;
		System.out.println();
		while(ind != null){
			System.out.print(ind.val);
			ind = ind.next;
		}
		System.out.println();
	}
	
	/**
	 * Equals leetcode is interleaving in LeetCode_day15
	 * 
	 * We are given 3 strings: str1, str2, and str3. 
	 * Str3 is said to be a shuffle of str1 and str2 
	 * if it can be formed by interleaving the characters of str1 
	 * and str2 in a way that maintains the left to right ordering 
	 * of the characters from each string.
	 * Ex: str1=abc, str2=def, str3=dabecf ---->valid
	 * 
	 * Analysis:
	 * Original
	 * Divide and Conquer
	 * if(s3[i1+i2+1] == s1[i1+1]) search (i1+1, i2)
	 * if(s3[i1+i2+1] == s2[i2+1]) search (i1, i2+1)
	 * 
	 * If the first characters of str1 and str3 are the same, 
	 * then we’ll recurse with new str1 and str3 being all but first 
	 * characters of the strings, and str2 will stay the same. 
	 * If first characters of str2 and str3 are the same, then we’ll do the 
	 * same thing with new str2 and str3 being all but first characters, 
	 * and str1 the same. Now this is the same problem with shorter strings, 
	 * so it’s very suitable for recursion. If neither str1′s nor str2′s first 
	 * character equals str3′s first character, we return false. 
	 * The base case of the recursion is, if any of the strings is empty 
	 * then the concatenation of str1 and str2 should be equal to str3.
	 * 
	 * The recursion method will fail on large tests.
	 * When A = XXX, B = XXX, C = XXXXXX, we can see many overlapping subproblems
	 * 
	 * A better implementation would be dynamic programming
	 * @param str1
	 * @param str2
	 * @param str3
	 */
	public static boolean combineTwoStringsRecursion(String str1, String str2, String str3, int ind1, int ind2, int ind3){
		if(str1.length() + str2.length() != str3.length()) return false;
		if(ind1 > str1.length() || ind2 > str2.length() || ind3 > str3.length()) return false;
		if(ind3 == str3.length() && ind1 == str1.length() && ind2 == str2.length()) return true;

		if(ind1 < str1.length() && str1.charAt(ind1) == str3.charAt(ind3) && combineTwoStringsRecursion(str1, str2, str3, ind1+1, ind2, ind3+1)) return true;
		if(ind2 < str2.length() && str2.charAt(ind2) == str3.charAt(ind3) && combineTwoStringsRecursion(str1, str2, str3, ind1, ind2+1, ind3+1)) return true;
		return false;
	}
	
	/**
	 * 2D dynamic programming O(mn) (mn subproblems)
	 * A typical way of solving dp is to find the state and the optimal function
	 * State:
	 * A[i][j] = true means s3[i+j] can be formed by s1[i] & s2[j] (i,j starts from 1)
	 * In code, we need to modify this because it starts at 0
	 * Optimal function:
	 * A[i][j] = (s3[i+j]==s1[i] && A[i-1][j]) || (s3[i+j]==s2[j] && A[i][j-1])
	 * 从矩阵的角度来看的话，每一个元素的值，依赖于它的上边和左边两个值。
	 * 
	 * @param str1
	 * @param str2
	 * @param str3
	 * @return
	 */
	public static boolean combineTwoStringsIterative(String str1, String str2, String str3){
		if(str1.length() + str2.length() != str3.length()) return false;
		
		boolean[][] A = new boolean[str1.length()+1][str2.length()+1];
		A[0][0] = true;
		for(int i = 1 ; i <= str1.length() ; i++)
			if(str1.charAt(i-1) == str3.charAt(i-1)) A[i][0] = true;
		for(int j = 1 ; j <= str2.length() ; j++)
			if(str2.charAt(j-1) == str3.charAt(j-1)) A[0][j] = true;
		for(int i = 1 ; i <= str1.length() ; i++){
			for(int j = 1 ; j <= str2.length() ; j++)
				A[i][j] = ( (A[i][j-1] && (str2.charAt(j-1) == str3.charAt(i+j-1)))
						|| (A[i-1][j] && (str1.charAt(i-1) == str3.charAt(i+j-1))) );
		}
		return A[str1.length()][str2.length()];
	}
	
	/**
	 * ! 1D dynamic programming, following method above.
	 * We don't need a 2D A matrix to record
	 * 
	 * @param str1
	 * @param str2
	 * @param str3
	 * @return
	 */
	public static boolean combineTwoStringIterative2(String str1, String str2, String str3){
		int l1 = str1.length(), l2 = str2.length() , l3 = str3.length();
		if(l1 + l2 != l3) return false;
		
		if(l2 > l1){//make sure str2 is shorter than str1
			String temp = str2; str2 = str1; str1 = temp;
			l2 = l1 ^ l2; l1 = l1 ^ l2; l2 = l1 ^ l2;
		}
		boolean[] isPrefix = new boolean[l2+1];
		isPrefix[0] = true;
		for(int i = 1 ; i <= l2 ; i++) 
			//isPrefix[i] = str2.substring(0,i).equals(str3.substring(0, i));
			isPrefix[i] = isPrefix[i-1] && str2.charAt(i-1) == str3.charAt(i-1);
		
		for(int i = 1 ; i <= l1 ; i++){
			isPrefix[0] = isPrefix[0] && str1.charAt(i-1) == str3.charAt(i-1);
			//isPrefix[0] = s1.substr(0, i)==s3.substr(0,i);
			for(int j = 1; j <= l2 ; j++){
				isPrefix[j] = ((isPrefix[j-1] && str2.charAt(j-1)==str3.charAt(i+j-1)) || 
						(isPrefix[j] && str1.charAt(i-1) == str3.charAt(i+j-1)));
			}
		}
		return isPrefix[l2];
	}
	
	/**
	 * Given a binary tree, check whether it's binary search tree or not.
	 * 
	 * Analysis: just in-order traverse
	 */
	public static boolean binarySearchTreeCheck(BTNode<Number> node){
		if(node == null) return true;
		if(node.left != null) 
			if(! binarySearchTreeCheck(node.left)) return false;
		if(node.left.val.doubleValue() > node.val.doubleValue()) return false;
		return binarySearchTreeCheck(node.right);
	}
	
	public static void main(String[] args) {
		System.out.println(findMissingElement(new int[]{1,2,2,4,5,6}, new int[]{1,2,4,5,6}));
		ListNode head = new ListNode(5);
		head.next = new ListNode(5);
		head.next.next = new ListNode(5);
		head.next.next.next = new ListNode(1);
		linkedListRemoveNodes(head,5);
	}

}


/**
 * No, it's not true. You could measure the performance
 *  by timing each loop for a large number of iterations, 
 * but I'm fairly certain they will be the same.
The myth came from C where ++i was regarded as faster than i++ 
because the former can be implemented by incremeting i then returning it. 
The latter might be implemented by copying the value of i to
 a temporary variable, incrementing i, then returning the temporary. 
 The first version doesn't need to make the temporary copy and so many 
 people assume that it is faster. However if the expression is used as a statement
  modern C compilers can optimize the temporary copy away so that 
  there will be no difference in practice.
*/
